//
//  插入排序.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/3/1.
//  时间复杂度n^2，原地稳定排序

import Foundation

/// 插入排序(从小到大)
/// - Parameter arr: 待排序的数组
/// - Returns: 排序后的数组
func insertionSort(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }
    
    var a = arr
    for i in 1..<a.count {
        let value = a[i]
        var j = i - 1
        // 查找插入的位置
        while j >= 0 && a[j] > value {
            a[j + 1] = a[j] // 数据移动
            j -= 1
        }
        a[j + 1] = value // 插入数据
    }
    
    return a
}

/// 折半插入排序(从小到大)
/// 优化一：折半插入排序（Binary Insertion Sort）是对插入排序算法的一种改进，所谓排序算法过程，就是不断的依次将元素插入前面已排好序的序列中，在寻找插入点时采用了折半查找。时间复杂度：O(n^2)，稳定性：稳定。
/// 排序思想：有一组数据待排序，排序区间为Array[0]~Array[n-1]。将数据分为有序数据和无序数据，第一次排序时默认Array[0]为有序数据，Array[1]~Array[n-1]为无序数据。有序数据分区的第一个元素位置为low，最后一个元素的位置为high。遍历无序区间的所有元素，每次取无序区间的第一个元素Array[i]，因为0~i-1是有序排列的，所以用中点m将其平分为两部分，然后将待排序数据同中间位置为m的数据进行比较，若待排序数据较大，则low~m-1分区的数据都比待排序数据小，反之，若待排序数据较小，则m+1~high分区的数据都比 待排序数据大，此时将low或high重新定义为新的合适分区的边界，对新的小分区重复上面操作。直到low和high 的前后顺序改变，此时high+1所处位置为待排序数据的合适位置。
/// - Parameter arr: 待排序的数组
/// - Returns: 排序后的数组
func binaryInsertionSort(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }
    
    var a = arr
    var j, temp, m, low, high: Int
    for i in 1..<a.count {
        temp = a[i]
        low = 0
        high = i - 1
        while low <= high {
            m = (low + high) / 2
            if a[m] > temp {
                high = m - 1
            } else {
                low = m + 1
            }
        }
        // 统一移动元素，然后将这个元素插入到正确的位置
        j = i
        while j > high + 1 {
            a[j] = a[j - 1] // 数据移动
            j -= 1
        }
        a[high + 1] = temp
    }
    
    return a
}

/// 希尔排序(从小到大)(不是稳定排序)希尔排序时间复杂度的下界是n*log2n
/// 优化二：希尔排序法是对直接插入排序法的优化，通过设置一个增量，对原始序列进行分组，对每组用直接插入排序法排序再整合，再缩小增量，周而复始直至增量为1，完成排序，因此又叫“缩小增量排序法”。其实到希尔算法进行到最后，n的值变为1（即增量或者称跳跃数变为1）的时候，它就是直接插入排序，只不过这时候，整个序列基本上是有序的，需要交换的数据已经非常少了，提高效率。
/// - Parameter arr: 待排序的数组
/// - Returns: 排序后的数组
func shellSort(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }
    
    var a = arr
    var gap = a.count / 2
    while gap > 0 {
        for i in gap..<a.count {
            let temp = a[i]
            var j = i - gap
            while j >= 0 && a[j] > temp {
                a[j + gap] = a[j]
                j -= gap
            }
            a[j + gap] = temp
        }
        gap /= 2
    }
    return a
}
